package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.LinkedList;
import java.util.TreeSet;

/**
 * @author Fengkai
 * @creat 2023/4/21
 * 给定参数n
 * 从1到n会有n个整数 1，2，3，...n
 * 这n个数字共有n!种排列 按大小顺序升序列出所有排列情况
 * 并一一标记
 * 当n = 3 时，所有排列如下
 * "123","132","213","231","312","321"
 * 给定n和k返回第n个排列
 * 输入
 * 第一行为n
 * 第二行为k
 * n 的范围是 1 ~ 9
 * k 的范围是 1 ~ n!
 * 输出
 * 输出排列第k位置的数字
 */
public class FindNSort {
    public static void main (String[] args) {
        System.out.println(findNSort(2, 2));

    }

    public static int findNSort (int n, int k) {
        TreeSet<Integer> integers = new TreeSet<>();
        if (n > 9) {
            return -1;
        }
        LinkedList<String> strings = new LinkedList<>();
        int[] ints = new int[n];
        for (int i = 1; i <= n; i++) {
            ints[i - 1] = i;
        }
        boolean[] dp = new boolean[n];
        int index = 0;
        dfs(index, dp, ints, strings, integers);
        int result = 0;
        while (k > 0) {
            result = integers.pollFirst();
            k--;
        }
        return result;
    }

    private static void dfs (int index, boolean[] dp, int[] ints, LinkedList<String> strings, TreeSet<Integer> integers) {
        if (index == ints.length) {
            StringBuilder stringBuilder = new StringBuilder();
            strings.stream().forEach(v -> {
                stringBuilder.append(v);
            });
            integers.add(Integer.parseInt(stringBuilder.toString()));
            return;
        }
        for (int i = 0; i < ints.length; i++) {
            if (dp[i]) {
                continue;
            }
            dp[i] = true;
            strings.addLast(String.valueOf(ints[i]));
            dfs(index + 1, dp, ints, strings, integers);
            strings.removeLast();
            dp[i] = false;
        }
    }
}
